/**
 * @author wxy
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {3,2,5,8,12,1,90,33,100};
        sort(arr,0,arr.length-1);
        for(int i = 0;i<arr.length;i++){
            System.out.print(arr[i]+",");
        }
    }


    //以一个数为基准，然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值

    public static void sort(int [] arr,int left,int right) {
        if (left < right) {
            int pivot = arr[left];
            int low = left;
            int high = right;
            while (low < high) {
                while (low < high && arr[high] > pivot) {
                    high--;
                }
                arr[low] = arr[high];
                while (arr[low] < pivot && low < high) {
                    low++;
                }
                arr[high] = arr[low];
            }
            arr[low] = pivot;
            sort(arr, left, low);
            sort(arr, low + 1, right);
        }
    }
}
